#ifndef ADJIACENCY_LIST_H
#define ADJIACENCY_LIST_H

#include <list>
#include <unordered_map>
#include <vector>
#include <iostream>
#include <cassert>

// 记录边的权重和顶点信息（无权图则不使用weight属性）
template<typename V>
struct weighted_EdgeNode
{
    V start; /// 第一个顶点
    V end; /// 第二个顶点
    double weight; /// 边的权重
    
    weighted_EdgeNode(const V & _start, const V & _end, double _weight = 0)
	: start{_start}, end{_end}, weight{_weight}
	{ }
    // 重载等于运算符
    bool operator ==(const weighted_EdgeNode<V> & node) const
	{
	    return (start == node.start && end == node.end && weight == node.weight);
	}
};

// V -- 图顶点的数据类型
template<typename V>
class Adjiacency_List
{
private:
    bool isDirected; /// 标识是否是有向图，默认为false
    bool isWeighted; /// 标识是否是有权图，默认为false
    size_t size; /// 顶点个数
    std::vector<V> vertices; /// 存储顶点
    
    std::vector<std::vector<V>> edge_vertices; // 存储边
    std::vector<double> edge_weight; // 存储边的权重（无权图则不使用）

    typedef weighted_EdgeNode<V> WEdgeNode;
    typedef std::list<WEdgeNode> WList;
    typedef std::unordered_map<V,WList> WTable;
    WTable LinkTable; /// 邻接表

    // 查找输入边的顶点是否存在
    bool find_vertex(const V & v);

public:
    Adjiacency_List(const std::vector<V> & vertices, bool _isDirected = false, bool _isWeighted = false);
    // 向图中添加一条边
    void add_edge(const V & v1, const V & v2); /// 无权图
    void add_edge(const V & v1, const V & v2, double weight); /// 有权图
    // 输出图中所有顶点
    void list_vertices();
    // 输出图中所有边
    void list_edges();
    // 打印整个图
    void print_graph();
    // 图的顶点个数
    size_t num_vertices()
	{
	    return size;
	}
    // 图的边数
    size_t num_edges();
};

// 构造函数，并初始化数据
template<typename V>
Adjiacency_List<V>::Adjiacency_List(const std::vector<V> & _vertices, bool _isDirected, bool _isWeighted) : vertices{_vertices}, isDirected{_isDirected}, isWeighted{_isWeighted}
{
    size = vertices.size();
    // 初始化邻接表
    for (int i = 0; i < size; ++i)
    {
	V _vertex = vertices[i];
	WList _list;
	LinkTable[_vertex] = _list;
    }
}

// 无权图
template<typename V>
void Adjiacency_List<V>::add_edge(const V & v1, const V & v2)
{
    // 只有无权图才能使用
    if(isWeighted)
    {
	std::cerr << "This is an unweighted graph!" << std::endl;
	assert(false);
    }

    // 判断v1和v2是否存在
    if(!(find_vertex(v1) && find_vertex(v2)))
    {
	std::cerr << "There is at least a vertex that not exists!" << std::endl;
	assert(false);
    }

    WEdgeNode node(v1,v2);
    LinkTable[v1].push_back(node);
    LinkTable[v1].unique(); /// 避免重复加边

    // 如果是无向图，还需要添加对称的一条边
    if (!isDirected)
    {
	// 无向图不能有loop
	if(v1 == v2)
	{
	    std::cerr << "Undirected graph can't have a loop!" << std::endl;
	    assert("false");
	}
	
	WEdgeNode _node(v2,v1);
	LinkTable[v2].push_back(_node);
	LinkTable[v2].unique(); /// 避免重复加边
    }

    // 保存边的信息
    std::vector<V> edge{v1,v2};
    // 检测是否有重复的边
    int sign = 0;
    for(typename std::vector<std::vector<V>>::iterator it = edge_vertices.begin(); it != edge_vertices.end(); ++it)
    {
	if(*it == edge)
	{
	    sign = 1;
	    break;
	}
    }
    if(!sign)
	edge_vertices.push_back(edge);
}

// 有权图
template<typename V>
void Adjiacency_List<V>::add_edge(const V & v1, const V & v2, double weight)
{
    // 只有有权图才能使用
    if(!isWeighted)
    {
	std::cerr << "This is a weighted graph!" << std::endl;
	assert(false);
    }

    // 判断v1和v2是否存在
    if(!(find_vertex(v1) && find_vertex(v2)))
    {
	std::cerr << "There is at least a vertex that not exists!" << std::endl;
	assert(false);
    }

    WEdgeNode node(v1,v2,weight);
    LinkTable[v1].push_back(node);
    LinkTable[v1].unique(); /// 避免重复加边

    // 如果是无向图，还需要补充对称点的信息
    if (!isDirected)
    {
	// 无向图不能有loop
	if(v1 == v2)
	{
	    std::cerr << "Undirected graph can't have a loop!" << std::endl;
	    assert("false");
	}
	
	WEdgeNode _node(v2,v1,weight);
	LinkTable[v2].push_back(_node);
	LinkTable[v2].unique(); /// 避免重复加边
    }

    // 保存边的信息
    std::vector<V> edge{v1,v2};
    // 检测是否有重复的边
    int sign = 0;
    int cnt = 0;
    for(typename std::vector<std::vector<V>>::iterator it = edge_vertices.begin(); it != edge_vertices.end(); ++it, ++cnt)
    {
	if(*it == edge)
	{
	    sign = 1;
	    break;
	}
    }
    // 无重复边
    if(!sign)
    {	    
	edge_vertices.push_back(edge);
	edge_weight.push_back(weight);
    }
    else //有重复边
    {
	// 权重不同，则更改权重
	if(edge_weight[cnt] != weight)
	    edge_weight[cnt] = weight;
    }
}

template<typename V>
void Adjiacency_List<V>::list_vertices()
{
    std::cout << "vertex set:\t";
    for(const auto & v : vertices)
	std::cout << v << " ";
    std::cout << "\b" << std::endl;
}

template<typename V>
void Adjiacency_List<V>::list_edges()
{
    std::cout << "edge set:\t";
    // 无权图
    if(!isWeighted)
    {
	for(const auto & v : edge_vertices)
	    std::cout << "(" << v[0] << "," << v[1] << ") ";
	std::cout << "\b" << std::endl;
    }
    else{  // 有权图
	size_t len = edge_vertices.size();
	for(int i = 0; i < len; ++i)
	    std::cout << "(" << edge_vertices[i][0] << "," << edge_vertices[i][1] << "," << edge_weight[i] << ") ";
	std::cout << "\b" << std::endl;
    }
}

template<typename V>
void Adjiacency_List<V>::print_graph()
{
    std::cout << "graph:" << std::endl;
    
    // 无向图
    if(!isDirected)
    {
	// 无权图
	if(!isWeighted)
	{
	    for(const auto & x : LinkTable)
	    {
		std::cout << x.first << " <--> ";
		WList _list = x.second;
		for(typename WList::iterator it = _list.begin(); it != _list.end(); ++it)
		    std::cout << (*it).end << " ";
		std::cout << "\b" << std::endl;
	    }
	}
	else{ // 有权图
	    for(const auto & x : LinkTable)
	    {
		std::cout << x.first << " <--> ";
		WList _list = x.second;
		for(typename WList::iterator it = _list.begin(); it != _list.end(); ++it)
		    std::cout << "(" << (*it).end << "," << (*it).weight << ") ";
		std::cout << "\b" << std::endl;
	    }
	}
    }
    else // 有向图
    {
	// 无权图
	if(!isWeighted)
	{
	    for(const auto & x : LinkTable)
	    {
		std::cout << x.first << " --> ";
		WList _list = x.second;
		for(typename WList::iterator it = _list.begin(); it != _list.end(); ++it)
		    std::cout << (*it).end << " ";
		std::cout << "\b" << std::endl;
	    }
	}
	else{ // 有权图
	    for(const auto & x : LinkTable)
	    {
		std::cout << x.first << " --> ";
		WList _list = x.second;
		for(typename WList::iterator it = _list.begin(); it != _list.end(); ++it)
		    std::cout << "(" << (*it).end << "," << (*it).weight << ") ";
		std::cout << "\b" << std::endl;
	    }
	}
    }
}

template<typename V>
size_t Adjiacency_List<V>::num_edges()
{
    
    return edge_vertices.size();
}

template<typename V>
bool Adjiacency_List<V>::find_vertex(const V & v)
{
    for (int idx = 0; idx < size; ++idx)
    {
        if (vertices[idx] == v)
            return true;
    }
    return false;
}

#else
#endif
